The present invention concerns, in general terms, a method and device for processing data, notably the representation, generation, restitution, regeneration or iterative processing of data.
More particularly, the present invention relates to the transmission (that is to say the representation at a distance) and/or the storage (that is to say the representation in a memory) of data, with or without compression thereof. These data can advantageously consist in the digital or analogue data of an image or sequence of images, and/or the digital or analogue data relating to sound (music, speech, etc), and/or the digital or analogue data relating to any mono or multidimensional signal.
Before disclosing the objectives and means of the invention, it is proposed below to give the following definitions:
xe2x80x9cSet of dataxe2x80x9d: set of any data representing physical quantities (usually voltage levels) which can themselves represent other physically perceptible or measurable quantities. In favoured applications, the sets of data concerned are images, sound or mono or multidimensional signals, etc. In the application relating to image processing, reference will sometimes be made to the xe2x80x9cimagexe2x80x9d instead of the xe2x80x9cset of dataxe2x80x9d relating to the image. That which will be disclosed below with regard to xe2x80x9cimagesxe2x80x9d or xe2x80x9csub-imagesxe2x80x9d is respectively applicable to xe2x80x9csets of dataxe2x80x9d or xe2x80x9csub-sets of dataxe2x80x9d and vice versa.
xe2x80x9cRepresentation of dataxe2x80x9d: any xe2x80x9cprocessingxe2x80x9d of a set of data of a given type, resulting from the perfect or imperfect transformation of the said set of data into another type. For example: the data can consist in the 256 grey levels of the pixels of an image, their representation consisting of a series of binary words able to be stored or transmitted; conversely, the representation of the data consisting of the said binary words can consist in their transformation in order to regain data of the same type as the initial data.
xe2x80x9cPrimary representationxe2x80x9d: by convention, any processing resulting from the transformation of the data of a first type to data of a second type. In this case a xe2x80x9cprimary processingxe2x80x9d of the data will be spoken of.
xe2x80x9cSecondary representationxe2x80x9d: by convention, the transformation of data of the second type resulting from a primary processing. In this case a xe2x80x9csecondary processingxe2x80x9d will be spoken of.
xe2x80x9cRestitution of dataxe2x80x9d: the particular case of a secondary representation in which the data of the second type are transformed into data of the first type. This restitution can be perfect or imperfect.
A xe2x80x9cmetric spacexe2x80x9d is a set of elements with a functional distance which is symmetrical, positive and satisfies triangular inequality. This space is xe2x80x9ccompletexe2x80x9d when it contains all the limit points of all the convergent series.
A xe2x80x9cLipschitz mappingxe2x80x9d: a mapping which transforms the points of a metric space in the same space and for which all the ratios of the distance of two elements transformed by the said mapping to the distance of the two said elements is limited.
A xe2x80x9ccontractive mappingxe2x80x9d or xe2x80x9ccontractionxe2x80x9d: a Lipschitz mapping for which the smallest of the majorants (contraction factor) of the said set of ratios is less than unity. However, within the meaning of the present invention, all the convergent mappings, that is to say those having a fixed point (thus enabling successive approximations to be used) in a sub-set of the metric space are contractive.
A xe2x80x9csimilarityxe2x80x9d is a Lipschitz mapping for which the ratio of the distance of two transformed elements to the distance of the said elements is a fixed quantity. A linear similarity is a xe2x80x9csimilitudexe2x80x9d.
A xe2x80x9ccontractive similarityxe2x80x9d is a Lipschitz mapping for which the ratio of the distance of two transformed elements to the distance of the said elements is a fixed quantity strictly less than unity.
The xe2x80x9cfixed pointxe2x80x9d of a contraction of a complete metric space in the same space (or of a sub-set of this space in itself) is the sole element which is left invariant by the said contractive mapping.
The xe2x80x9cconstructionxe2x80x9d of a contractive mapping on a set of data consists in forming a family of contractions able to transform the data and selecting the parameters of one of the said contractions in order to satisfy one or more predetermined conditions.
The xe2x80x9cmethod of successive approximationsxe2x80x9d makes it possible to approach, iteratively, as close as wished, the fixed point of a contraction. Starting from an arbitrary element, the said contraction is applied thereto. The same contraction is then applied to the previously obtained transform. By reiterating this process, the fixed point of the contraction is approached successively and ineluctably.
xe2x80x9cA better approximationxe2x80x9d of an element in a metric space is a point in a sub-set of candidates, which are themselves points in the said space, which minimises the distance to the said element.
xe2x80x9cA good approximationxe2x80x9d of an element in a metric space is a point in a sub-set in the said space which is close, with a predetermined error, to a predetermined best approximation.
Various image representation methods, with compression, using the fractal technique, are known in the state of the art.
Through the document U.S. Pat. No. 5,065,447, a method and device are known for processing or storing an image with compression of the data relating to the initial image. In this method, the data relating to the initial image are divided, that is to say the image is divided into a plurality of elementary sub-images (referred to as xe2x80x9cdomain blocksxe2x80x9d). This method next consists in generating an ordered dictionary of a set of reference sub-images (referred to as xe2x80x9crange blocksxe2x80x9d) formed from portions of an image of predetermined size which has undergone a certain number of predetermined operations such as rotation and turning about various axes of symmetry. Next, for each elementary sub-image a comparison is made with all the reference sub-images of the dictionary and the reference sub-image which is the most similar to the elementary sub-image under consideration is selected from the dictionary. Finally, the method consists in processing or storing parametric information relating to the addresses of the reference sub-images selected from the dictionary, in order to represent each of the original elementary sub-images.
It is through this set of operations that the method described in this document makes it possible to obtain a first representation of the image with compression of the data.
In order to effect, from the said parametric information, the restitution of the initial image, the method and device described in this document perform the following operations: from an initial arbitrary image, steps similar to those above are carried out, that is to say the initial arbitrary image is partitioned and a dictionary is formed from the elementary sub-images thereof. However, the dictionary is formed only partially, performing for each sub-image only the predetermined operation corresponding to the relevant address of the dictionary for the position of the sub-image under consideration.
The data thus obtained are used for reiterating this process until the difference between two consecutively obtained images is less than a predetermined threshold. The image obtained lastly is then an approximation of the initial image.
This method, which is of interest on a theoretical level, has the major drawback that it is sometimes difficult to put into practice on an industrial level with the means known at the present time. This is because each image necessarily involves a lengthy analysis with the creation of a particularly large dictionary, the elementary sub-images of the image to be stored or transmitted all being compared with each of the reference sub-images present in the dictionary. The inventors, who carried out simulations, thus found that, for certain images of average size and resolution (512xc3x97512 pixels with 3xc3x97256 colour levels), the processing time for compression was around 1000 to 2000 seconds on a workstation, that is to say around half an hour. Such a processing time is obviously prohibitive for almost any industrial application.
Through the document WO-A-93/17519, another method and device for image processing with compression of the data relating to the initial image are known. In this method the data relating to the initial image are also partitioned, that is to say the image is divided into a plurality of elementary sub-images (referred to as xe2x80x9cdomainsxe2x80x9d). In this method a set of fractal transforms linking the sub-images to the set of initial data is next determined, that is to say a portion of the image similar to the elementary image under consideration is sought in the initial image, so as to minimise the error between the initial data and the approximate data item thus obtained. The coefficients of the set of fractal transformations thus produced constitute the first representation of the initial image.
In order to effect the restitution of the image, the method and device described in this document seek the fixed points of the elementary fractal transformations whose coefficients were received, without however explaining how this search is carried out. The initial image is thus restored by assembling the restored sub-images.
This method is also of interest on a theoretical level. However, the inventors found significant degradations of the quality of the restored image.
The inventors have sought to develop a data processing method of the same type as the methods of the state of the art analysed above, but having better performance both with regard to the quality of the restored data and with regard to the processing speed.
During their research, the inventors discovered that the reason why the methods described in U.S. Pat. No. 5,065,447 and WO-A-93/17519 have the above-mentioned defects relates to the fact that the two methods involve geometric transformations of portions of images consisting essentially of contractive similarities (construction of the dictionary in U.S. Pat. No. 5,065,447 and fractal transformation in WO-A-93/17519). They were in fact able to show that it is a question in both cases of using an idea broadly shared by persons skilled in the art interested in fractal compression at the time of filing of the present application, an idea according to which the images, whatever their origin, consist essentially of elements or parts having themselves significant degrees of resemblance.
However, the performance of WO-A-93/17519 is in fact very weak with regard to the quality of the image restored, since the inventors discovered that the capabilities for the restitution of contractive similitudes are very limited, contrary to the belief of the said persons skilled in the art of the date of filing of the present application.
Likewise the performance of U.S. Pat. No. 5,065,447 are very limited with regard to processing time. As the capabilities for the restitution of contractive similitudes are intrinsically limited, the author of U.S. Pat. No. 5,065,447 is led to set up a large dictionary which is constructed on the basis of numerous transformations of sub-images in the method according to U.S. Pat. No. 5,065,447: it is a case in fact of artificially multiplying the resemblance elements, which certainly makes it possible to substantially improve the quality of the restored image, but at the expense of the calculation time.
The inventors have therefore sought to produce a method and device for the processing of data, notably of images, making it possible to obtain better performance than the aforementioned state of the art both with regard to the quality of the data or of the restored image and with regard to calculation speed, and able to result in a significant compression of the data to be transmitted or stored.
In cases where the images to be compressed or restored are very large, the devices known at the present time, which use data of all parts of the image, must have available a large memory space, which makes them expensive and slow.
In general terms, according to a fist aspect, the present invention relates to a method for the primary processing of a first set of primary data representing physical quantities, characterised in that it includes:
a set division step during which the first set of data is divided into first sub-sets of data, and
for each first sub-set of data:
a step of xe2x80x9cconstructingxe2x80x9d a first type of global contractive mapping, for the said first sub-set of data, whose fixed point constitutes an approximation of all or part of this sub-set,
using, to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, and
determining parameters of the global contractive mapping so as to allow the use, on a second sub-set of data, of a method of successive approximations converging towards the fixed point of a second type of global contractive mapping;
the set of parameters thus determined constituting a primary representation of the said first set of data.
In general terms, according to a second aspect, the present invention relates to a device for the primary processing of a first set of primary data representing physical quantities, characterised in that it has:
a means of inputting primary data,
a set division means adapted to divide the first set of data into first sub-sets of data, and
a construction means adapted, for each first sub-set of data, to construct a first type of global contractive mapping, for the said first sub-set of data, whose fixed point constitutes an approximation of all or part of this sub-set,
using, to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, and
determining parameters of the global contractive mapping so as to allow the use, on a second sub-set of data, of a method of successive approximations converging towards the fixed point of a second type of global contractive mapping; and
a means of outputting the set of parameters thus determined, parameters which constitute a primary representation of the said first set of data.
Owing to these provisions, the sub-sets of first data being processed successively, the memory space used, and, in particular, the fast memory space, is reduced. The method of the invention can therefore be implemented on all systems, independently of their memory capacity.
In addition, the sets of primary data of large size can thus be processed in pieces, each piece corresponding to a first sub-set of data. Likewise, the method of successive approximations can be implemented in pieces.
Finally, when it is desired to restore only part of the image constituting the set of primary data, for example in a case where it is desired to display part of an image, the invention makes it possible to consider only the parameters associated with the first sub-sets of primary data which contain the said image part.
In addition, in accordance with the invention, in order to process, and notably to represent, a set of initial data representing physical quantities, notably with compression of the said initial data, it suffices to construct, by appropriate means, a global contractive mapping, acting on the said data.
Another important characteristic of the invention lies in the fact that, in order to construct the said global contractive mapping, it is necessary to use at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings. In doing this, any recourse to mathematical transformations belonging to the class of contractive similarities is excluded, which makes it possible to avoid the drawbacks mentioned above.
However, in order to construct the said global contractive mapping acting on the data, a person skilled in the art has a very wide range of mathematical tools which he can use. He can consequently choose from amongst these tools those which are the most favourable to performance, for example in conjunction with the type of data to be represented or the particular mapping concerned. Such a possibility does not exist in the state of the art analysed above and proves very advantageous. Thus, for example, in the case of a local processing of the image, by partitioning the latter into elementary sub-images, a person skilled in the art can choose, for the local processing, mappings which are not necessarily contractive, which gives him an important choice in the possibilities of local processing of the image and thus leaves him great freedom. In particular, he can choose, at the local level, Lipschitz mappings which will enable him to facilitate the use of the contractive nature of the global mapping.
In addition, the use of a method of successive approximations leaves a person skilled in the art the freedom to choose the final distance between the said fixed point and the data thus restored or generated.
By avoiding the formation of a dictionary and the lengthy analysis described in the document U.S. Pat. No. 5,065,447, and owing to the characteristics of the present invention, the processing of an image is notably accelerated compared with the aforementioned US document. By implementing their preferred embodiment, the inventors found that, for an image of 512xc3x97512 pixels with 3xc3x97256 colour levels, the processing time was approximately less than 100 seconds on a workstation; they also have every reason to believe that the improvements made to the method and device briefly defined above will make it possible to obtain performance with regard to speed.
It should also be noted that, since the constructed elementary mappings belong to the group of mappings consisting of multidimensional mappings and non-linear mappings, the mappings belonging to the class of similitudes are avoided, with the advantages observed above.
According to a third aspect, the present invention relates to a method for the secondary processing of several sub-sets of parameters, characterised in that it includes:
for each sub-set of parameters, an xe2x80x9citerative calculationxe2x80x9d step during which, using the said sub-set of parameters, there is implemented, on a second sub-set of data, a method of successive approximations converging towards the fixed point of a second type of global contractive mapping, using, to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, and
an assembly step during which the fixed points resulting from the iterative calculation made on each sub-set of parameters are combined, in order to constitute a secondary representation of the sets of parameters.
According to a fourth aspect, the present invention relates to a device for the secondary processing of several sub-sets of parameters, characterised in that it has:
calculation means adapted, for each sub-set of parameters, to effect an iterative calculation using the said sub-set of parameters and on a second sub-set of data, in order to implement a method of successive approximations converging towards the fixed point of a second type of global contractive mapping, using, to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, and
an assembly means adapted to combine the fixed points resulting from the iterative calculation made on each sub-set of parameters, in order to constitute a secondary representation of the sets of parameters.
These aspects of the invention have the same advantages as those set out above. They are therefore not repeated here.
In addition, the method of successive approximations used for the secondary processing is implemented in a particularly simple fashion using the parameters obtained at the end of the primary processing, because these parameters are independent of the dimensions of the elementary sub-set with which they are associated. The inventors found, in the field of image processing with compression, good performance both with regard to the quality of the restored image and with regard to the processing speed mentioned above.
The present invention also aims to remedy an other problem where the compressed images subsequently give rise to decompressions which are liable to have different resolutions or different image dimensions, the devices of the prior art require the use of all the compressed data, which impairs their speed and efficiency.
According to a fifth aspect, the present invention relates to a method for the primary processing of a set of data representing physical quantities, a primary processing method taking into account a minimum dimension and including an xe2x80x9cinitial partitioningxe2x80x9d step during which the said set of data is partitioned into initial elementary sub-sets,
a primary processing method characterised in that it includes:
a) for each elementary sub-set which does not have the said minimum dimension, at least one iteration of a sequence of steps including:
a step of estimating suitability of division, during which a suitability of division of the said elementary sub-set is estimated, and
when the suitability estimation does not meet predetermined quality criteria, a step of xe2x80x9cpost-partitioningxe2x80x9d of the said sub-set into intermediate elementary sub-sets,
b) a xe2x80x9cconstructionxe2x80x9d step in which, for each of the elementary sub-sets, whether it results from the initial partitioning or from a post-partitioning and whether or not it has itself been the subject of a post-partitioning, an elementary mapping is constructed in the elementary sub-set under consideration, determining the parameters of the elementary mapping so as:
to make contractive a first type of global mapping, for the said set of data, a global mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, the restrictions of the global mapping to the elementary sub-sets consisting of the said elementary mappings, the fixed point of the global mapping constituting an approximation of all or part of this set,
to allow the use of a method of successive approximations converging towards the fixed point of the said global contractive mapping; all the parameters thus determined, as well as, when at least one post-partitioning step has taken place, an item of partitioning information, representing each said post-partitioning, constituting conjointly a primary representation of the said set of data.
According to a sixth aspect, the present invention relates to a device for the primary processing of a set of data representing physical quantities, taking into account a minimum dimension, characterised in that it has:
an initial partitioning means adapted to partition the said set of data into initial elementary sub-sets,
calculation means adapted, for each elementary sub-set which does not have the said minimum dimension, to effect at least one iteration of a sequence of steps including:
a step of estimating suitability of division during which a suitability of division of the said elementary sub-set is estimated, and
when the suitability estimation does not meet predetermined quality criteria, a step of xe2x80x9cpost-partitioningxe2x80x9d of the said sub-set into intermediate elementary sub-sets,
a xe2x80x9cconstructionxe2x80x9d means adapted, for each of the elementary sub-sets, whether it results from the initial partitioning or from a post-partitioning and whether or not it has itself been the subject of a post-partitioning, to construct an elementary mapping in the elementary sub-set under consideration, determining the parameters of the elementary mapping so as:
to make contractive a first type of global mapping, for the said set of data, a global mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, the restrictions of the global mapping to the elementary sub-sets consisting of the said elementary mappings, the fixed point of the global mapping constituting an approximation of all or part of this set,
to allow the use of a method of successive approximations converging towards the fixed point of the said global contractive mapping;
an output means adapted to transmit the set of parameters thus determined, as well as, when at least one post-partitioning step has taken place, an item of partitioning information, representing each said post-partitioning in order to constitute conjointly a primary representation of the said set of data.
By virtue of these provisions, since the primary representation includes all the parameters related to all the elementary sub-sets, whether or not they have given rise to a post-partitioning, it will be possible to sort the parameters which it is wished to process as a function of the dimension of the elementary sub-set to which they are related.
If it is wished to restore the set of primary data with, for the restitution, a smaller size than that of the set of primary data, it will be possible not to take account of the parameters relating to the smallest elementary sub-sets.
On the other hand, if it is wished to restore the set of primary data with, for the restitution, a larger size than that of the set of primary data, it will be possible to take account of all the parameters constituting the primary representation.
Likewise, depending on the fineness of the details which it is wished to restore (fineness related to the resolution), it will be possible to take into account more or fewer parameters, as a function of the size of the elementary sub-sets with which they are associated.
According to a seventh aspect, the present invention relates to a method for the secondary processing of a set of parameters associated with at least one item of partitioning information, resulting from a primary processing of a first set of data, a secondary processing method characterised in that it includes:
a step of determining a minimum dimension of elementary sub-sets,
a step of determining elementary sub-sets constituting a partitioning of a second set of data, a step taking into account on the one hand the said minimum dimension and on the other hand the presence of partitioning information corresponding to the said sub-sets,
a step of selecting, from the set of parameters, parameters associated with the said determined elementary-sets, and
an xe2x80x9citerative calculationxe2x80x9d step during which, using the selected parameters and the determined elementary sub-sets, use is made, on the second set of data, of a method of successive approximations converging towards the fixed point of a global contractive mapping of the second type, the restrictions of the global mapping to the elementary sub-sets consisting of the said elementary mappings, using, to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings.
According to a eighth aspect, the present invention relates to a device for the secondary processing of a set of parameters associated with at least one item of partitioning information, resulting from a primary processing of a first set of data, characterised in that it has:
a means of determining a minimum dimension of elementary sub-sets,
a means of determining elementary sub-sets constituting a partitioning of a second set of data, a means taking into account on the one hand the said minimum dimension and on the other hand the presence of partitioning information corresponding to the said sub-sets,
a means of selecting, from the set of parameters, parameters associated with the said determined elementary-sets, and
calculation means adapted to effect iterative calculations, using the selected parameters and the determined elementary sub-sets, in order to implement, on the second set of data, a method of successive approximations converging towards the fixed point of a global contractive mapping of the second type, the restrictions of the global mapping to the elementary sub-sets consisting of the said elementary mappings, using, to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings.
These aspects of the invention have the same advantages as those set out above. They are therefore not repeated here.
The present invention also aims to remedy an other technical problem: where several images must be decompressed and displayed simultaneously, the known devices of the prior art require the opening of as many files as there are images to be decompressed, which makes the decompression operation slow.
According to a ninth aspect, the present invention relates to a method for the primary processing of at least two sets of primary data representing physical quantities, referred to as xe2x80x9cfirst sets of dataxe2x80x9d, characterised in that it includes, for each first set of data:
a step of xe2x80x9cconstructingxe2x80x9d a first type of global contractive mapping, for the said first set of data, whose fixed point constitutes an approximation of all or part of this set,
using, to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, and
determining parameters of the global contractive mapping so as to allow the use, on a second set of data, of a method of successive approximations converging towards the fixed point of a second type of global contractive mapping;
a step of organising a computer file including data representing each set of parameters resulting from a construction step applied to each first set of data, the parameters thus organised in a file constituting a primary representation of the said first sets of data.
According to a tenth aspect, the present invention relates to a device for the primary processing for at least two sets of primary data representing physical quantities, referred to as xe2x80x9cfirst sets of dataxe2x80x9d, characterised in that it has:
a means of inputting primary data,
a construction means adapted, for each first set of data, to construct a first type of global contractive mapping, for the said first set of data, whose fixed point constitutes an approximation of all or part of this sub-set,
using, to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, and
determining parameters of the global contractive mapping so as to allow the use, on a second set of data, of a method of successive approximations converging towards the fixed point of a second type of global contractive mapping; and
an organisation means adapted to organise a computer file including data representing each set of parameters resulting from a construction step applied to each first set of data, the parameters thus organised in a file constituting a primary representation of the said first sets of data.
Owing to these provisions, since a file is organised with parameters relating to several sets of data, when it is desired to gain access simultaneously to parameters relating to different sets of data, for example in order to display on a screen data dependent on these parameters, the opening of several computer files is avoided. The method according to the invention therefore affords a significant gain in time.
For example, when the parameters constitute compressed data relating to images, a rapid display of several decompressed images is possible.
According to an eleventh aspect, the present invention relates to a method for the secondary processing of a set of parameters resulting from a primary processing of a first set of data, a secondary processing method characterised in that it includes:
a step of reading from a file, during which at least part of the set of parameters is read from a file common to several sets of parameters, and
an xe2x80x9citerative calculationxe2x80x9d step during which, using the said set of parameters, a method of successive approximations converging towards the fixed point of a global contractive mapping of the second type is implemented on a second set of data using, in order to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, this fixed point constituting a secondary representation of the said first set of data.
According to a twelfth aspect, the present invention relates to a device for the secondary processing of a set of parameters resulting from a primary processing of a first set of data, characterised in that it has:
a means of reading from a file, adapted to read at least part of the set of parameters from a file common to several sets of parameters, and
calculation means adapted to effect iterative calculations, using the said set of parameters, in order to implement, on a second set of data, a method of successive approximations converging towards the fixed point of a global contractive mapping, using, to do this, at least one mapping belonging to the group of mappings consisting of multidimensional mappings and non-linear mappings, this fixed point constituting a secondary representation of the said first set of data.
These aspects of the invention have the same advantages as those set out above. They are therefore not restated here.
The invention also relates to a printer, a photocopier, a camera and a facsimile device including a processing device as succinctly disclosed above.
The invention also relates to a memory which stores:
parameters and partitioning information resulting from a primary processing as succinctly disclosed above, and
instructions for software making it possible to implement a secondary processing method as succinctly disclosed above.
The advantages of these devices and memory being identical to those disclosed above, they are not repeated here.